home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / Moscow ML 1.42 / examples / lexyacc / README < prev   
Encoding:
Text File  |  1997-08-18  |  6.9 KB  |  185 lines  |  [TEXT/R*ch]
  1. GRAMMAR FOR A SIMPLE FUNCTIONAL LANGUAGE    Peter Sestoft
  2. ----------------------------------------        KVL 1996-01-26, 1996-12-06
  3.  
  4. The files in this directory present lexer and parser specifications
  5. for the simple lazy functional language CL (Peyton Jones and Lester,
  6. Prentice Hall 1992).
  7.  
  8.     File        contents
  9.     --------------------------------------------------------
  10.     README      describes the grammar and the lexical conventions,
  11.                 and gives an example (this file)
  12.     Lexer.lex   the lexer specification
  13.     Parser.grm  the parser specification
  14.     Data.sml    describes the abstract syntax datatype
  15.     Main.sml    uses the generated lexer and parser 
  16.     cl/         example source files for parsing
  17.  
  18.  
  19. Generating, compiling, and using the lexer and parser
  20. -----------------------------------------------------
  21.  
  22. You may type `make' to perform steps 1-4 below.
  23.  
  24. 1. Generate the parser
  25.     mosmlyac Parser.grm
  26.  
  27. 2. Generate the lexer
  28.     mosmllex Lexer.lex
  29.  
  30. 3. Compile lexer, parser and auxiliary programs
  31.     mosmlc -c Data.sml Parser.sig Parser.sml Lexer.sml Main.sml
  32.  
  33. 4. Load the compiled parser and lexer
  34.     mosml load
  35.  
  36. 5. Try them
  37.     parse "cl/nats.cl";
  38.     parse "cl/append.cl";
  39.     parse "cl/fibs.cl";
  40.     etc.
  41.  
  42.  
  43. THE GRAMMAR
  44. ===========
  45.  
  46. Expression:
  47.  
  48.   Expr     =  "let" Defns "in" Expr              let-binding
  49.            |  "letrec" Defns "in" Expr           recursive let-binding
  50.            |  "case" Expr "of" Alts "end"        case expression
  51.            |  "if" Expr "then" Expr "else" Expr  conditional expression
  52.            |  "\" Name "." Expr                  function
  53.            |  SExpr                              simple expression
  54.                                                  
  55. Simple expression:                               
  56.                                                  
  57.   SExpr    =  AppExpr                            application expression
  58.            |  SExpr "/" SExpr                    integer division
  59.            |  SExpr "%" SExpr                    integer remainder
  60.            |  SExpr "*" SExpr                    multiplication
  61.            |  SExpr "+" SExpr                    addition
  62.            |  SExpr "-" SExpr                    subtraction
  63.            |  SExpr "=" SExpr                    equality
  64.            |  SExpr "~=" SExpr                   inequality
  65.            |  SExpr "<" SExpr                    less than
  66.            |  SExpr "<=" SExpr                   less or equal
  67.            |  SExpr ">" SExpr                    greater than
  68.            |  SExpr ">=" SExpr                   greater or equal
  69.            |  SExpr "&" SExpr                    logical `and'
  70.            |  SExpr "|" SExpr                    logical `or'
  71.                                                  
  72. Application expression:                          
  73.                                                  
  74.   AppExpr  =  AExpr                              atomic expression
  75.            |  AppExpr AExpr                      application
  76.                                                  
  77. Atomic expression:                               
  78.                                                  
  79.   AExpr    =  Name                               variable
  80.            |  IntCst                             integer constant
  81.            |  "pack" "{" IntCst Exprs "}"        tagged data value
  82.            |  "(" Expr ")"                       parenthesized expr.
  83.                                                  
  84. Definition list:                                 
  85.                                                  
  86.   Defns    =  Defn                               single definition
  87.            |  Defn ";" Defns                     multiple definitions
  88.                                                  
  89. Definition:                                      
  90.                                                  
  91.   Defn     =  Name "=" Expr                      variable binding
  92.                                                  
  93. Alternative list:                                
  94.                                                  
  95.   Alts     =  Alt                                single alternative
  96.            |  Alt ";" Alts                       multiple alternatives
  97.                                                  
  98. Variable list:                                   
  99.                                                  
  100.   Vars     =                                     no variables  
  101.            |  Name Vars                          one or more variables
  102.                                                  
  103. Expression list:                                 
  104.                                                  
  105.   Exprs    =                                     no expressions
  106.            |  "," Expr Exprs                     one or more expressions
  107.  
  108.  
  109.  
  110. LEXICAL MATTERS
  111. ===============
  112.  
  113. Whitespace may appear between any two grammar symbols.
  114.  
  115. Comments (* ... *) may appear everywhere whitespace may appear;
  116. comments may be nested.
  117.  
  118. A variable name begins with a letter (lowercase or uppercase) and
  119. continues with letters or digits.
  120.  
  121. An integer constant consist of a non-empty sequence of the digits 0-9,
  122. possibly immediately preceded by a minus sign (~).
  123.  
  124.  
  125.  
  126. EXAMPLE PROGRAM
  127. ===============
  128.  
  129. The program below conforms to the grammar above.  Note that the
  130. program text may contain comments.  Comments and whitespace are
  131. removed by the lexer and therefore are not mentioned by the grammar.
  132.  
  133. There are more example programs in the subdirectory `cl'.
  134.  
  135. ----------------------------------------------------------------
  136. (* Stolen from Klaus Elmquist Nielsen, Copyright (c) 1993 *)
  137.  
  138. letrec
  139.    sieve = \xs.case xs of
  140.                <1>      -> pack {1} ;
  141.                <2> x xr -> pack {2, x, sieve (filter (\n.(n % x) ~= 0) xr)}
  142.                end ;
  143.  
  144.    take = \n.\xs.case xs of
  145.                  <1>      -> pack {1} ;
  146.                  <2> x xr -> if n=0 then pack {1}
  147.                              else pack {2, x, take (n-1) xr}
  148.                  end;
  149.  
  150.    filter = \p.\xs.case xs of
  151.                    <1>      -> pack {1} ;
  152.                    <2> x xr -> if p x then pack {2, x, filter p xr}
  153.                                else filter p xr
  154.                    end ;
  155.  
  156.    from = \n.pack {2, n, from (n+1)}
  157.  
  158. in take 200 (sieve (from 2))
  159. -----------------------------------------------------------------
  160.  
  161.  
  162.  
  163. THE MEANING OF CL PROGRAMS
  164. ==========================
  165.  
  166. As far as lexing and parsing are concerned, the *meaning* of
  167. expressions in the CL language does not matter.  However, for the
  168. curious student, we note that most things are familiar from SML, and
  169. that the following correspondences hold:
  170.  
  171.     CL expression                         SML expression
  172.     ----------------------------------------------------
  173.  
  174.     \x.e                corresponds to    fn x => e     
  175.  
  176.     pack{1}             corresponds to    []            
  177.  
  178.     pack{2, e1, e2}     corresponds to    e1::e2        
  179.  
  180.     case e0 of          )              (  case e0 of
  181.        <1>      -> e1;  ) corresponds  (     []    => e1
  182.        <2> x xr -> e2   )     to       (   | x::xr => e2
  183.     end                 )              (
  184.  
  185.